COM2109   Automata, Computation and Complexity   (20 credits)

Description

This module introduces the theoretical foundations for computing systems: finite state machines, pushdown automata, and Turing machines, along with the formal languages that can be recognised by these machine models. It also deals with the question 'What is computable?' and 'What is efficiently computable?' by showing when problems are computationally hard, and how to find algorithmic solutions to computationally hard problems.

Reading List